[算法]-搜索-二分查找、二叉查找树

发表于 | 分类于 | 阅读次数

高效检索信息是处理海量信息的前提，二分查找适用的数据结构是有序数组，还有二叉查找树，红黑树，和散列表三种数据类型来实现高效的查找。

二分查找

二分查找一个有序的数组,复杂度O(logn)

java实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public Integer binarySearch(int[] list, int key){
    int end = list.length-1;
    int begin = 0;
    int mid;
    while (begin<=end){
        mid =begin+(end-begin)/2;
        if (list[mid]==key) {
            return key;
        }
        if (list[mid]<key)
        {
            end = mid-1;
        }
        if (list[mid]>key){
            begin = mid+1;
        }
    }
    return null;
}

但实际上用int型查找型非常局限，为了拓展，我们用Comparable的对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class binarySearch<Key extends Comparable<Key>, Value> {

    public Key binarySearch(Key[] list, Key key){
        int end = list.length-1;
        int begin = 0;
        int mid;
        while (begin<=end){
            mid =begin+(end-begin)/2;
            if (list[mid].compareTo(key)==0) {
                return key;
            }
            if (list[mid].compareTo(key)>0)
            {
                end = mid-1;
            }
            if (list[mid].compareTo(key)<0){
                begin = mid+1;
            }
        }
        return null;
    }
}

二叉查找树

二叉树的每个节点都大于左子树的任意一个节点，小于右子树的任意一个节点。查找的最坏情况O(n),最好情况O（logn）

二叉查找树的生成和插入，非递归 java：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package algos;

/**
 * @author jiaxuehui
 * @version 1.0
 * @Description 二叉查找树
 * @Date 07/11/2018 5:01 PM
 */
public class binarySearchTree<T extends Comparable<T>> {
    public static class biNode<T extends Comparable<T>> {
        T value;
        biNode left = null;
        biNode right = null;
        public biNode(T v){
            this.value = v;
        }

        public T getDate () {
            return this.value;
        }

        public biNode getLeft () {
            return this.left;
        }

        public biNode getright () {
            return this.right;
        }
    }

       
    biNode root=null;
   
    public binarySearchTree(T val){
        root = new biNode(val);
    }

    public biNode insert( T val){
        biNode tmp =root;
        if (root.value.compareTo(val)<=0){
            while (tmp.right!=null && tmp.right.value.compareTo(val)<=0){
                tmp = tmp.right;
            }
            if (tmp.right == null){
                tmp.right = new biNode(val);
                return tmp.right;
            }
            tmp=tmp.right;
            biNode tmp2 = tmp.left;
            tmp.left = new biNode(val);
            tmp.left.left =tmp2;
            return tmp.left;
        }
        else {
            while (tmp.left!=null && tmp.left.value.compareTo(val)>=0){
                tmp = tmp.left;
            }
            if (tmp.left == null){
                tmp.left = new biNode(val);
                return tmp.left;
            }
            tmp = tmp.left;
            biNode tmp2 = tmp.right;
            tmp.right = new biNode(val);
            tmp.right.right =tmp2;
            return tmp.right;
        }
    }

    public void DFS(biNode root){ //先序遍历
        if(root!=null) {
            DFS(root.left);
            System.out.print(root.value+" ");
            DFS(root.right);
        }
    }

}

二叉查找树的搜索 递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public boolean search(biNode root, T val){
    if (root != null) {
        if (root.value.compareTo(val) > 0) {
            return search(root.left, val);
        }
        if (root.value.compareTo(val) < 0) {
            return search(root.right, val);
        }
        if (root.value.compareTo(val) == 0)
            return true;
    }
    return false;

}

二叉查找树最坏情况下的时间和树的高度成正比（O(n)），所以当最坏情况的性能还是很糟糕，所以我们可以用平衡树，能保证无论如何构造他她的运行时间都是对数级（树的高度是LogN）